package com.itheima.datastructure.linkedlist;

/**
 * 反转链表
 */
public class E01Leetcode206 {

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        ListNode n1 = new E01Leetcode206().reverseList(o1);
        System.out.println(n1);
    }
    // 方法1，构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加到新链表头部，完成后新链表即是倒序的。
    public ListNode reverseList1(ListNode o1) {
        ListNode n1 = null;    // 新单链表head
        ListNode p = o1;   // 旧链表head
        while (p != null){
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        return n1;
    }

    // 方法2，与方法1类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的，区别在于原题目
//    未提供节点外层的容器类，这里提供一个，另外一个区别是并不去构造新节点。
    public ListNode reverseList2(ListNode head) {
        List list1 = new List(head);
        List list2 = new List(null);

        while (true){
            ListNode first = list1.removeFirst();
            if (first == null){
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first){
            first.next = head;
            head = first;
        }

        public ListNode removeFirst(){
            ListNode first = head;
            if (first != null){
                head = first.next;
            }
            return first;
        }
    }

    // 方法3 - 递归
    public ListNode reverseList3(ListNode p) {
        if (p == null || p.next == null){
            return p;
        }
        ListNode last = reverseList3(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }

    // 方法4 - 从链表每次拿到第二个节点，将其从链表断开，插入头部，直到它为null 结束
    public ListNode reverseList4(ListNode o1) {
        // 1. 空链表  2. 一个元素
        if (o1 == null || o1.next == null){
            return o1;
        }
        ListNode o2 = o1.next;
        ListNode n1 = o1;
        while (o2 != null){
            // 2. 将 o2 节点从链表断开，即 o1 节点指向第三节点
            o1.next = o2.next;
            // 3. o2 节点链入链表头部，
            o2.next = n1;
            // 4. n1 指向 o2
            n1 = o2;
            // 5. o2 指向 o1 的下一个节点，
            o2 = o1.next;
        }
        return n1;
    }

    // 方法5 - 不断把 o1 头插到 n1 -- 把链表分成两部分，思路就是不断从链表2的头，往链表1的头搬移。
    public ListNode reverseList(ListNode o1) {
        // 1. n1 指向 null，代表**新链表**一开始没有元素，o1 指向**原链表**的首节点
        ListNode n1 = null;
        while (o1 != null){
            // 2. 开始循环，o2 指向**原链表**次节点
            ListNode o2 = o1.next;
            // 3. 搬移
            o1.next = n1;
            // 4. 指针复位
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }
}
